/*
题目: 划分为K个相等的子集
给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
 */
public class CanPartitionKSubsets {
    boolean[] visited = null; // 某个状态是否访问过
    int avg = 0, n = 0;
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // 记忆化搜索, n 比较小, 可以使用位运算
        n = nums.length;
        visited = new boolean[1 << n];

        int sum = 0;
        for (int x : nums)  sum += x;
        if (sum % k != 0) return false;

        this.avg = sum / k;
        Arrays.sort(nums);
        if (nums[n - 1] > avg)  return false;

        return backTrack(nums, (1 << n) - 1, 0); //
    }

    // 初识时 state = 0111111...., 用过为0, 没用过就为 1
    private boolean backTrack(int[] nums, int state, int bucket) {
        // 全都用完了
        if (state == 0) {
            return true;
        }
        // 第二次访问这个状态, 能成功就会返回 true, 说明肯定只能返回 false
        if (visited[state]) {
            return false;
        }
        // 标记为访问过
        visited[state] = true;
        for (int i = 0; i < n; i ++) {
            if ((state & (1 << i)) == 0) continue ;// 用过

            // 关键步骤 ! 直接让容量 限制死 在 avg 中, 也就起到了 平分成 K 份的效果
            if (bucket + nums[i] > avg) { // 已经没救了, 及时止损
                return false;
            }

            if (backTrack(nums, state ^ (1 << i), (bucket + nums[i]) % avg)) {
                return true;
            }
        }

        return false;
    }
}
